/*
 ------------------------------------------------------------------------------
 Copyright (C) 2013 Eternal Games.

 This file is part of the EternalTech source code.

 The EternalTech source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The EternalTech source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the EternalTech source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


//
// r_light.cpp - light management
//


#include "r_local.h"



#define MAX_LIGHT_VOLUME_POINTS		16

typedef struct {
	int		numPoints;
	glqVec3	points[MAX_LIGHT_VOLUME_POINTS << 1];
} lightVolume_t;

static void R_ClipLightFaceToCubeSide (lightVolume_t *lightVolume, int numPoints, glqVec3 *points, glqPlane planes[4], int stage){

	glqVec3	clipped[MAX_LIGHT_VOLUME_POINTS + 4];
	float	dists[MAX_LIGHT_VOLUME_POINTS + 4];
	int		sides[MAX_LIGHT_VOLUME_POINTS + 4];
	bool	frontSide, backSide;
	float	frac;
	int		numClipped;
	int		i, j;

	if (stage == 4){
		// Fully clipped
		if (numPoints < 3)
			return;

		// Add the points, ignoring duplicates
		for (i = 0; i < numPoints; i++){
			for (j = 0; j < lightVolume->numPoints; j++){
				if (lightVolume->points[j].Compare(points[i], ON_EPSILON))
					break;
			}

			if (j != lightVolume->numPoints)
				continue;

			// Add the point
			lightVolume->points[lightVolume->numPoints++] = points[i];
		}

		return;
	}

	// Determine sides for each point
	frontSide = false;
	backSide = false;

	for (i = 0; i < numPoints; i++){
		dists[i] = planes[stage].Distance(points[i]);

		if (dists[i] > ON_EPSILON){
			sides[i] = PLANESIDE_FRONT;
			frontSide = true;
			continue;
		}

		if (dists[i] < -ON_EPSILON){
			sides[i] = PLANESIDE_BACK;
			backSide = true;
			continue;
		}

		sides[i] = PLANESIDE_ON;
	}

	if (!frontSide)
		return;			// Not clipped

	if (!backSide){
		R_ClipLightFaceToCubeSide(lightVolume, numPoints, points, planes, stage + 1);
		return;
	}

	// Clip it
	if (numPoints >= MAX_LIGHT_VOLUME_POINTS - 2)
		Com_Error(false, "R_ClipLightFaceToCubeSide: MAX_LIGHT_VOLUME_POINTS hit");

	points[i] = points[0];

	dists[i] = dists[0];
	sides[i] = sides[0];

	numClipped = 0;

	for (i = 0; i < numPoints; i++){
		if (sides[i] == PLANESIDE_ON){
			clipped[numClipped++] = points[i];
			continue;
		}

		if (sides[i] == PLANESIDE_FRONT)
			clipped[numClipped++] = points[i];

		if (sides[i+1] == PLANESIDE_ON || sides[i+1] == sides[i])
			continue;

		if (dists[i] == dists[i+1])
			clipped[numClipped++] = points[i];
		else {
			frac = dists[i] / (dists[i] - dists[i+1]);

			clipped[numClipped++] = points[i] + (points[i+1] - points[i]) * frac;
		}
	}

	// Continue
	R_ClipLightFaceToCubeSide(lightVolume, numClipped, clipped, planes, stage + 1);
}

static void R_ShadowTestCrap (drawLight_t *dl){

	static glqAngles	cubeAngles[6] = {glqAngles(0.0f, 0.0f, 90.0f), glqAngles(0.0f, 180.0f, 90.0f), glqAngles(0.0f, 90.0f, 0.0f), glqAngles(0.0f, -90.0f, 0.0f), glqAngles(-90.0f, 90.0f, 0.0f), glqAngles(90.0f, 90.0f, 0.0f)};
	static int			cornerIndices[6][4] = {{3, 2, 6, 7}, {0, 1, 5, 4}, {2, 3, 1, 0}, {4, 5, 7, 6}, {1, 3, 7, 5}, {2, 0, 4, 6}};
	glqPlane			planes[4];
	glqMat3				axis;
	glqVec3				points[5];
	float				s, c;
	int					i, j;

	lightVolume_t	lightVolume;
	int				shadowCubeBits = 0;

	light_t	*light = dl->light;

	// For each side of the cube
	for (i = 0; i < 6; i++){

		// TODO: add a couple FOV degrees epsilon to account for filtering across cube faces?

		// TODO: these planes could be precomputed and static, only dist needs to be recomputed for each light

		axis = cubeAngles[i].ToMat3();

		// Set up the left/right clip planes
		glqMath::SinCos(92.0f * (M_PI_HALF / 180.0f), s, c);

		planes[0].SetNormal(axis[0] * s - axis[1] * c);
		planes[0].SetDist(light->data.origin.Dot(planes[0].Normal()));
		planes[0].SetSignBits();

		planes[1].SetNormal(axis[0] * s + axis[1] * c);
		planes[1].SetDist(light->data.origin.Dot(planes[1].Normal()));
		planes[1].SetSignBits();

		// Set up the top/bottom clip planes
		glqMath::SinCos(92.0f * (M_PI_HALF / 180.0f), s, c);

		planes[2].SetNormal(axis[0] * s - axis[2] * c);
		planes[2].SetDist(light->data.origin.Dot(planes[2].Normal()));
		planes[2].SetSignBits();

		planes[3].SetNormal(axis[0] * s + axis[2] * c);
		planes[3].SetDist(light->data.origin.Dot(planes[3].Normal()));
		planes[3].SetSignBits();

		// Clip the light volume to the frustum

		// TODO: only add the origin if it is inside the light volume
		lightVolume.numPoints = 1;
		lightVolume.points[0] = light->data.origin;

		for (j = 0; j < 6; j++){
			points[0] = light->data.corners[cornerIndices[j][0]];
			points[1] = light->data.corners[cornerIndices[j][1]];
			points[2] = light->data.corners[cornerIndices[j][2]];
			points[3] = light->data.corners[cornerIndices[j][3]];

			R_ClipLightFaceToCubeSide(&lightVolume, 4, points, planes, 0);
		}


		// TODO: store clipped volume for this side in light->data, then perform culling dynamically


		if (!lightVolume.numPoints)
			continue;


		glqPlane	*plane;
		int		side;
		int		k;

		for (j = 0, plane = rg.viewParms.frustum; j < NUM_FRUSTUM_PLANES; j++, plane++){
			if (!(rg.viewParms.planeBits & BIT(j)))
				continue;

			side = 0;

			for (k = 0; k < lightVolume.numPoints; k++){
				side |= plane->PointOnSide(lightVolume.points[k]);

				if (side != PLANESIDE_BACK)
					break;
			}

			if (side == PLANESIDE_BACK)
				break;		// return
		}

		if (j == NUM_FRUSTUM_PLANES)
			shadowCubeBits |= BIT(i);
	}

	dl->shadowCubeBits = shadowCubeBits;
}





/*
 ==================
 R_SetupLightData

 TODO: PVS
 ==================
*/
void R_SetupLightData (scene_t *scene, const renderLight_t *renderLight, lightData_t *lightData, bool inWorld){

	glqVec3	lVector, rVector;
	glqVec3	dVector, uVector;
	glqVec3	nVector, fVector;
	glqVec3	corner, direction;
	float	distance, maxDistance;
	float	ratio;
	int		i;

	if (lightData->valid)
		return;		// Already computed the light data

	lightData->valid = true;
	lightData->precached = false;

	// If the light data was precached, copy it and return immediately
	if (!r_skipLightCache->integerValue){
		if (R_PrecachedLightData(scene, renderLight, lightData))
			return;
	}

	// Set the material
	if (renderLight->material)
		lightData->material = renderLight->material;
	else {
		if (renderLight->type != RL_PROJECTED)
			lightData->material = rg.defaultLightMaterial;
		else
			lightData->material = rg.defaultProjectedLightMaterial;
	}

	// Compute the origin, direction, and axis
	if (renderLight->type == RL_POINT || renderLight->type == RL_CUBIC){
		lightData->origin = renderLight->origin + renderLight->axis * renderLight->center;
		lightData->direction.Clear();
		lightData->axis.Identity();
	}
	else if (renderLight->type == RL_PROJECTED){
		direction = -renderLight->axis[2];

		lightData->origin = renderLight->origin;
		lightData->direction = direction;
		lightData->axis = direction.ToMat3();
	}
	else {
		direction = -(renderLight->axis * renderLight->center);
		direction.Normalize();

		lightData->origin = renderLight->origin - direction * renderLight->radius.Length();
		lightData->direction = direction;
		lightData->axis = direction.ToMat3();
	}

	// Compute the bounding volume
	if (renderLight->type != RL_PROJECTED){
		// Compute the corner points
		for (i = 0; i < 8; i++){
			corner[0] = (i & 1) ? -renderLight->radius[0] : renderLight->radius[0];
			corner[1] = (i & 2) ? -renderLight->radius[1] : renderLight->radius[1];
			corner[2] = (i & 4) ? -renderLight->radius[2] : renderLight->radius[2];

			// Transform into world space
			R_LocalPointToWorld(corner, lightData->corners[i], renderLight->origin, renderLight->axis);
		}

		// Compute the bounding box
		lightData->bounds.FromPoints(lightData->corners);

		// Compute the frustum planes
		lightData->frustum[0].Set( renderLight->axis[0],  renderLight->origin.Dot(renderLight->axis[0]) - renderLight->radius[0]);
		lightData->frustum[1].Set(-renderLight->axis[0], -renderLight->origin.Dot(renderLight->axis[0]) - renderLight->radius[0]);
		lightData->frustum[2].Set( renderLight->axis[1],  renderLight->origin.Dot(renderLight->axis[1]) - renderLight->radius[1]);
		lightData->frustum[3].Set(-renderLight->axis[1], -renderLight->origin.Dot(renderLight->axis[1]) - renderLight->radius[1]);
		lightData->frustum[4].Set( renderLight->axis[2],  renderLight->origin.Dot(renderLight->axis[2]) - renderLight->radius[2]);
		lightData->frustum[5].Set(-renderLight->axis[2], -renderLight->origin.Dot(renderLight->axis[2]) - renderLight->radius[2]);
	}
	else {
		// Compute the corner points
		ratio = renderLight->zFar / renderLight->zNear;

		lVector = renderLight->axis[0] * renderLight->xMin;
		rVector = renderLight->axis[0] * renderLight->xMax;

		dVector = renderLight->axis[1] * renderLight->yMin;
		uVector = renderLight->axis[1] * renderLight->yMax;

		nVector = renderLight->axis[2] * renderLight->zNear;
		fVector = renderLight->axis[2] * renderLight->zFar;

		lightData->corners[0] = renderLight->origin - fVector - lVector * ratio - uVector * ratio;
		lightData->corners[1] = renderLight->origin - fVector - rVector * ratio - uVector * ratio;
		lightData->corners[2] = renderLight->origin - fVector - lVector * ratio - dVector * ratio;
		lightData->corners[3] = renderLight->origin - fVector - rVector * ratio - dVector * ratio;
		lightData->corners[4] = renderLight->origin - nVector - lVector - uVector;
		lightData->corners[5] = renderLight->origin - nVector - rVector - uVector;
		lightData->corners[6] = renderLight->origin - nVector - lVector - dVector;
		lightData->corners[7] = renderLight->origin - nVector - rVector - dVector;

		// Compute the bounding box
		lightData->bounds.FromPoints(lightData->corners);

		// Compute the frustum planes
		lightData->frustum[0].SetFromPoints(lightData->corners[6], lightData->corners[2], lightData->corners[3]);
		lightData->frustum[1].SetFromPoints(lightData->corners[5], lightData->corners[1], lightData->corners[0]);
		lightData->frustum[2].SetFromPoints(lightData->corners[1], lightData->corners[3], lightData->corners[2]);
		lightData->frustum[3].SetFromPoints(lightData->corners[7], lightData->corners[5], lightData->corners[4]);
		lightData->frustum[4].SetFromPoints(lightData->corners[7], lightData->corners[3], lightData->corners[1]);
		lightData->frustum[5].SetFromPoints(lightData->corners[4], lightData->corners[0], lightData->corners[2]);
	}

	// Compute the light range
	maxDistance = 0.0f;

	if (renderLight->type != RL_DIRECTIONAL){
		for (i = 0; i < 8; i++){
			distance = lightData->origin.Distance(lightData->corners[i]);

			if (distance > maxDistance)
				maxDistance = distance;
		}
	}
	else {
		for (i = 0; i < 8; i++){
			distance = lightData->direction.Dot(lightData->corners[i]) - lightData->direction.Dot(lightData->origin);

			if (distance > maxDistance)
				maxDistance = distance;
		}
	}

	lightData->lightRange = maxDistance + 8.0f;

	// Compute the fog plane
	lightData->fogPlane.SetFromPoints(lightData->corners[2], lightData->corners[3], lightData->corners[1]);

	// Compute the shadow bias and jitter scales
	if (renderLight->type == RL_PROJECTED){
		lightData->shadowBiasScale.Set(2.5f);
		lightData->shadowJitterScale.Set(0.01f * renderLight->zNear / (renderLight->xMax - renderLight->xMin), 0.01f * renderLight->zNear / (renderLight->yMax - renderLight->yMin));
	}
	else if (renderLight->type == RL_POINT || renderLight->type == RL_CUBIC){
		lightData->shadowBiasScale.Set(2.5f);
		lightData->shadowJitterScale.Set(0.01f);
	}
	else {
		lightData->shadowBiasScale.Set(2.5f);
		lightData->shadowJitterScale.Set(0.8f);
	}

	// Compute the transformation matrices
	if (renderLight->type != RL_PROJECTED){
		lightData->projectionMatrix[0][0] = 0.5f / renderLight->radius[0];
		lightData->projectionMatrix[0][1] = 0.0f;
		lightData->projectionMatrix[0][2] = 0.0f;
		lightData->projectionMatrix[0][3] = 0.0f;
		lightData->projectionMatrix[1][0] = 0.0f;
		lightData->projectionMatrix[1][1] = 0.5f / renderLight->radius[1];
		lightData->projectionMatrix[1][2] = 0.0f;
		lightData->projectionMatrix[1][3] = 0.0f;
		lightData->projectionMatrix[2][0] = 0.0f;
		lightData->projectionMatrix[2][1] = 0.0f;
		lightData->projectionMatrix[2][2] = 0.5f / renderLight->radius[2];
		lightData->projectionMatrix[2][3] = 0.0f;
		lightData->projectionMatrix[3][0] = 0.5f;
		lightData->projectionMatrix[3][1] = 0.5f;
		lightData->projectionMatrix[3][2] = 0.5f;
		lightData->projectionMatrix[3][3] = 1.0f;

		lightData->modelviewMatrix[0][0] = -renderLight->axis[0][0];
		lightData->modelviewMatrix[0][1] = renderLight->axis[1][0];
		lightData->modelviewMatrix[0][2] = -renderLight->axis[2][0];
		lightData->modelviewMatrix[0][3] = 0.0f;
		lightData->modelviewMatrix[1][0] = -renderLight->axis[0][1];
		lightData->modelviewMatrix[1][1] = renderLight->axis[1][1];
		lightData->modelviewMatrix[1][2] = -renderLight->axis[2][1];
		lightData->modelviewMatrix[1][3] = 0.0f;
		lightData->modelviewMatrix[2][0] = -renderLight->axis[0][2];
		lightData->modelviewMatrix[2][1] = renderLight->axis[1][2];
		lightData->modelviewMatrix[2][2] = -renderLight->axis[2][2];
		lightData->modelviewMatrix[2][3] = 0.0f;
		lightData->modelviewMatrix[3][0] = renderLight->origin.Dot(renderLight->axis[0]);
		lightData->modelviewMatrix[3][1] = -renderLight->origin.Dot(renderLight->axis[1]);
		lightData->modelviewMatrix[3][2] = renderLight->origin.Dot(renderLight->axis[2]);
		lightData->modelviewMatrix[3][3] = 1.0f;

		lightData->modelviewProjectionMatrix = lightData->projectionMatrix * lightData->modelviewMatrix;
	}
	else {
		lightData->projectionMatrix[0][0] = 0.5f * (2.0f * renderLight->zNear / (renderLight->xMax - renderLight->xMin));
		lightData->projectionMatrix[0][1] = 0.0f;
		lightData->projectionMatrix[0][2] = 0.0f;
		lightData->projectionMatrix[0][3] = 0.0f;
		lightData->projectionMatrix[1][0] = 0.0f;
		lightData->projectionMatrix[1][1] = -0.5f * (2.0f * renderLight->zNear / (renderLight->yMax - renderLight->yMin));
		lightData->projectionMatrix[1][2] = 0.0f;
		lightData->projectionMatrix[1][3] = 0.0f;
		lightData->projectionMatrix[2][0] = 0.5f * ((renderLight->xMax + renderLight->xMin) / (renderLight->xMax - renderLight->xMin)) - 0.5f;
		lightData->projectionMatrix[2][1] = -0.5f * ((renderLight->yMax + renderLight->yMin) / (renderLight->yMax - renderLight->yMin)) - 0.5f;
		lightData->projectionMatrix[2][2] = 1.0f / (renderLight->zFar - renderLight->zNear);
		lightData->projectionMatrix[2][3] = -1.0f;
		lightData->projectionMatrix[3][0] = 0.0f;
		lightData->projectionMatrix[3][1] = 0.0f;
		lightData->projectionMatrix[3][2] = -0.5f * ((renderLight->zFar + renderLight->zNear) / (renderLight->zFar - renderLight->zNear)) + 0.5f;
		lightData->projectionMatrix[3][3] = 0.0f;

		lightData->modelviewMatrix[0][0] = renderLight->axis[0][0];
		lightData->modelviewMatrix[0][1] = renderLight->axis[1][0];
		lightData->modelviewMatrix[0][2] = -renderLight->axis[2][0];
		lightData->modelviewMatrix[0][3] = 0.0f;
		lightData->modelviewMatrix[1][0] = renderLight->axis[0][1];
		lightData->modelviewMatrix[1][1] = renderLight->axis[1][1];
		lightData->modelviewMatrix[1][2] = -renderLight->axis[2][1];
		lightData->modelviewMatrix[1][3] = 0.0f;
		lightData->modelviewMatrix[2][0] = renderLight->axis[0][2];
		lightData->modelviewMatrix[2][1] = renderLight->axis[1][2];
		lightData->modelviewMatrix[2][2] = -renderLight->axis[2][2];
		lightData->modelviewMatrix[2][3] = 0.0f;
		lightData->modelviewMatrix[3][0] = -renderLight->origin.Dot(renderLight->axis[0]);
		lightData->modelviewMatrix[3][1] = -renderLight->origin.Dot(renderLight->axis[1]);
		lightData->modelviewMatrix[3][2] = renderLight->origin.Dot(renderLight->axis[2]);
		lightData->modelviewMatrix[3][3] = 1.0f;

		lightData->modelviewProjectionMatrix = lightData->projectionMatrix * lightData->modelviewMatrix;
	}

	// Set up the PVS

	// Clear the precached nodes
	lightData->nodes = NULL;
}

/*
 ==================
 R_CullLightBounds
 ==================
*/
static int R_CullLightBounds (lightData_t *lightData, int planeBits){

	glqPlane	*plane;
	int			side, cullBits;
	int			i;

	cullBits = CULL_IN;

	// Check against frustum planes
	for (i = 0, plane = rg.viewParms.frustum; i < NUM_FRUSTUM_PLANES; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = plane->BoundsOnSide(lightData->bounds);

		if (side == PLANESIDE_BACK){
			rg.pc.cullBoundsOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits != CULL_IN)
		rg.pc.cullBoundsClip++;
	else
		rg.pc.cullBoundsIn++;

	return cullBits;
}

/*
 ==================
 R_CullLightVolume
 ==================
*/
static int R_CullLightVolume (lightData_t *lightData, int planeBits){

	glqPlane	*plane;
	int			side, cullBits;
	int			i, j;

	cullBits = CULL_IN;

	// Check against frustum planes
	for (i = 0, plane = rg.viewParms.frustum; i < NUM_FRUSTUM_PLANES; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = 0;

		for (j = 0; j < 8; j++){
			side |= plane->PointOnSide(lightData->corners[j]);

			if (side == PLANESIDE_CROSS)
				break;
		}

		if (side == PLANESIDE_BACK){
			rg.pc.cullBoundsOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits != CULL_IN)
		rg.pc.cullBoundsClip++;
	else
		rg.pc.cullBoundsIn++;

	return cullBits;
}

/*
 ==================
 R_ViewInLightVolume

 Returns true if the view is inside the light volume
 ==================
*/
static bool R_ViewInLightVolume (lightData_t *lightData){

	glqPlane	*plane;
	int			i;

	// Check for bounds intersection
	if (!lightData->bounds.ContainsPoint(rg.renderView.origin))
		return false;

	// Check against frustum planes
	for (i = 0, plane = lightData->frustum; i < 6; i++, plane++){
		if (plane->PointOnSide(rg.renderView.origin) == PLANESIDE_BACK)
			return false;
	}

	return true;
}


/*
 ==============================================================================

 LIGHT FRUSTUM CULLING

 ==============================================================================
*/


/*
 ==================
 R_LightCullBounds
 ==================
*/
int R_LightCullBounds (lightData_t *lightData, const glqBounds &bounds, int planeBits){

	glqPlane	*plane;
	int			side, cullBits;
	int			i;

	cullBits = CULL_IN;

	// Check against frustum planes
	for (i = 0, plane = lightData->frustum; i < 6; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = plane->BoundsOnSide(bounds);

		if (side == PLANESIDE_BACK){
			rg.pc.cullBoundsOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits != CULL_IN)
		rg.pc.cullBoundsClip++;
	else
		rg.pc.cullBoundsIn++;

	return cullBits;
}

/*
 ==================
 R_LightCullLocalBounds
 ==================
*/
int R_LightCullLocalBounds (lightData_t *lightData, const glqBounds &bounds, const glqVec3 &origin, const glqMat3 &axis, int planeBits){
 
	glqPlane	*plane;
	glqVec3		corner, worldCorners[8];
	int			side, cullBits;
	int			i, j;

	cullBits = CULL_IN;

	// Compute the corner points
	for (i = 0; i < 8; i++){
		corner[0] = (i & 1) ? bounds[0][0] : bounds[1][0];
		corner[1] = (i & 2) ? bounds[0][1] : bounds[1][1];
		corner[2] = (i & 4) ? bounds[0][2] : bounds[1][2];

		// Transform into world space
		R_LocalPointToWorld(corner, worldCorners[i], origin, axis);
	}

	// Check against frustum planes
	for (i = 0, plane = lightData->frustum; i < 6; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = 0;

		for (j = 0; j < 8; j++){
			side |= plane->PointOnSide(worldCorners[j]);

			if (side == PLANESIDE_CROSS)
				break;
		}

		if (side == PLANESIDE_BACK){
			rg.pc.cullBoundsOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits != CULL_IN)
		rg.pc.cullBoundsClip++;
	else
		rg.pc.cullBoundsIn++;

	return cullBits;
}


/*
 ==============================================================================

 SCISSOR REGION

 ==============================================================================
*/


/*
 ==================
 R_SetupScissor
 ==================
*/
static void R_SetupScissor (drawLight_t *dl){

	static int	cornerIndices[6][4] = {{3, 2, 6, 7}, {0, 1, 5, 4}, {2, 3, 1, 0}, {4, 5, 7, 6}, {1, 3, 7, 5}, {2, 0, 4, 6}};
	glqVec3		points[2][MAX_POLYGON_POINTS];
	int			numPoints;
	glqBounds	bounds;
	glqVec3		ndc;
	int			pingPong = 0;
	int			i, j;

	// If scissor testing is disabled
	if (r_skipLightScissors->integerValue){
		dl->scissor = rg.viewParms.scissor;
		return;
	}

	// Clip the light volume to the view frustum
	bounds.Clear();

	for (i = 0; i < 6; i++){
		numPoints = 4;

		points[pingPong][0] = dl->light->data.corners[cornerIndices[i][0]];
		points[pingPong][1] = dl->light->data.corners[cornerIndices[i][1]];
		points[pingPong][2] = dl->light->data.corners[cornerIndices[i][2]];
		points[pingPong][3] = dl->light->data.corners[cornerIndices[i][3]];

		for (j = 0; j < NUM_FRUSTUM_PLANES; j++){
			if (!(rg.viewParms.planeBits & BIT(j)))
				continue;

			if (!R_ClipPolygon(numPoints, points[pingPong], rg.viewParms.frustum[j], ON_EPSILON, &numPoints, points[!pingPong]))
				break;

			pingPong ^= 1;
		}

		if (j != NUM_FRUSTUM_PLANES)
			continue;

		// Add the clipped points
		for (j = 0; j < numPoints; j++){
			// Transform into normalized device coordinates
			R_TransformWorldToDevice(points[pingPong][j], ndc, rg.viewParms.modelviewProjectionMatrix);

			// Add it
			bounds.AddPoint(ndc);
		}
	}

	if (bounds.IsCleared()){
		dl->scissor.Zero();
		return;
	}

	// Transform into screen space
	R_TransformDeviceToScreen(bounds[0], bounds[0], rg.viewParms.viewport);
	R_TransformDeviceToScreen(bounds[1], bounds[1], rg.viewParms.viewport);

	// Set up the scissor
	dl->scissor.FromBounds(bounds);
	dl->scissor.ExpandSelf(1);
	dl->scissor.Clip(rg.viewParms.scissor);

	if (dl->scissor.IsCleared()){
		dl->scissor.Zero();
		return;
	}
}


/*
 ==============================================================================

 SHADOW LOD

 ==============================================================================
*/


/*
 ==================
 R_SetupShadowLOD
 ==================
*/
static void R_SetupShadowLOD (drawLight_t *dl){

	glqPlane	*plane;
	glqBounds	bounds;
	glqVec3		ndc;
	float		distance, minDistance;
	float		frac;
	int			size, lod;
	int			x, y;
	int			i;

	// If it doesn't cast shadows, don't bother with it
	if (dl->light->l.noShadows || (dl->material->flags & MF_NOSHADOWS)){
		dl->shadowLOD = -1;
		dl->shadowFilter = -1;

		return;
	}

	// If a directional light, use the lowest LOD level
	if (dl->light->l.type == RL_DIRECTIONAL){
		dl->shadowLOD = 0;
		dl->shadowFilter = r_shadowFilter->integerValue;

		return;
	}

	// Find the screen region that the light volume covers
	bounds.Clear();

	for (i = 0; i < 8; i++){
		// Transform into normalized device coordinates
		R_TransformWorldToDevice(dl->light->data.corners[i], ndc, rg.viewParms.modelviewProjectionMatrix);

		// Add it
		bounds.AddPoint(ndc);
	}

	if (bounds.IsCleared()){
		dl->shadowLOD = -1;
		dl->shadowFilter = -1;

		return;
	}

	// Transform into screen space
	R_TransformDeviceToScreen(bounds[0], bounds[0], rg.viewParms.viewport);
	R_TransformDeviceToScreen(bounds[1], bounds[1], rg.viewParms.viewport);

	// Find the largest size
	x = glqMath::FloatToInt(glqMath::Ceil(bounds[1][0]) - glqMath::Floor(bounds[0][0]));
	y = glqMath::FloatToInt(glqMath::Ceil(bounds[1][1]) - glqMath::Floor(bounds[0][1]));

	size = Max(x, y);

	// Compute fraction of screen covered
	if (rg.viewParms.viewport.Width() <= rg.viewParms.viewport.Height())
		frac = (float)size / rg.viewParms.viewport.Width();
	else
		frac = (float)size / rg.viewParms.viewport.Height();

	// Determine LOD level
	lod = NUM_SHADOW_BUFFERS - glqMath::FloatToInt(frac * NUM_SHADOW_BUFFERS);
	if (lod < 0)
		lod = 0;

	if (lod == NUM_SHADOW_BUFFERS){
		// If the screen region was too small, don't bother with it
		if (frac < 0.025f){
			dl->shadowLOD = -1;
			dl->shadowFilter = -1;

			return;
		}

		// See how far the light volume is
		plane = &rg.viewParms.frustum[FRUSTUM_NEAR];

		minDistance = M_INFINITY;

		for (i = 0; i < 8; i++){
			distance = plane->Distance(dl->light->data.corners[i]);

			if (distance < minDistance)
				minDistance = distance;
		}

		// If too far, don't cast shadows at all
		if (minDistance > MAX_SHADOW_DISTANCE * 0.5f){
			dl->shadowLOD = -1;
			dl->shadowFilter = -1;

			return;
		}

		lod--;
	}

	dl->shadowLOD = lod;

	// Also determine filtering quality
	dl->shadowFilter = Max(r_shadowFilter->integerValue - (lod >> 1), 0);
}


/*
 ==============================================================================

 CUBE BITS

 ==============================================================================
*/


/*
 ==================
 
 ==================
*/
static void R_SetupCubeBits (drawLight_t *dl){

	if (dl->light->l.type != RL_POINT && dl->light->l.type != RL_CUBIC)
		return;

	// If it doesn't cast shadows, don't bother with it
	if (dl->light->l.noShadows || (dl->material->flags & MF_NOSHADOWS))
		return;

	// FIXME!!!
	R_ShadowTestCrap(dl);
}


/*
 ==============================================================================

 SHADOW SPLITS

 ==============================================================================
*/


/*
 ==================
 R_SetupShadowSplits
 ==================
*/
static void R_SetupShadowSplits (drawLight_t *dl){

	static float	distanceScales[MAX_SHADOW_SPLITS] = {0.015625f, 0.0375f, 0.0875f, 0.20f, 0.45f, 1.0f};
	glqMat3			nAxis, fAxis;
	glqVec3			corners[8];
	glqVec4			xVector, yVector;
	float			xCenter, yCenter;
	float			xScale, yScale;
	float			xTan, yTan;
	glqVec3			center;
	float			radius;
	float			xMin, xMax;
	float			yMin, yMax;
	float			zNear, zFar;
	float			distance;
	int				i, j;

	if (dl->light->l.type != RL_DIRECTIONAL)
		return;

	// If it doesn't cast shadows, don't bother with it
	if (dl->light->l.noShadows || (dl->material->flags & MF_NOSHADOWS))
		return;

	dl->numShadowSplits = 0;

	// Set the tangents
	xTan = glqMath::Tan(rg.viewParms.fovX * (M_PI / 360.0f));
	yTan = glqMath::Tan(rg.viewParms.fovY * (M_PI / 360.0f));

	// Set the scales
	xScale = 0.5f * rg.shadowArrayTexture->width;
	yScale = 0.5f * rg.shadowArrayTexture->height;

	// Set the vectors
	xVector[0] = -dl->light->data.axis[1][0];
	xVector[1] = -dl->light->data.axis[1][1];
	xVector[2] = -dl->light->data.axis[1][2];
	xVector[3] = dl->light->data.origin.Dot(dl->light->data.axis[1]);

	yVector[0] = dl->light->data.axis[2][0];
	yVector[1] = dl->light->data.axis[2][1];
	yVector[2] = dl->light->data.axis[2][2];
	yVector[3] = -dl->light->data.origin.Dot(dl->light->data.axis[2]);

	// Split the view frustum
	for (i = 0; i < MAX_SHADOW_SPLITS; i++){
		if (i == 0)
			zNear = r_zNear->floatValue;
		else {
			if (rg.viewParms.zFar <= zFar)
				break;

			zNear = zFar;
		}

		zFar = (MAX_SHADOW_DISTANCE * distanceScales[i]) / rg.viewParms.fovScale;

		// Compute the split corner points
		nAxis[0] = rg.renderView.axis[0] * zNear;
		nAxis[1] = rg.renderView.axis[1] * zNear * xTan;
		nAxis[2] = rg.renderView.axis[2] * zNear * yTan;

		fAxis[0] = rg.renderView.axis[0] * zFar;
		fAxis[1] = rg.renderView.axis[1] * zFar * xTan;
		fAxis[2] = rg.renderView.axis[2] * zFar * yTan;

		corners[0] = rg.renderView.origin + nAxis[0] + nAxis[1] + nAxis[2];
		corners[1] = rg.renderView.origin + nAxis[0] - nAxis[1] + nAxis[2];
		corners[2] = rg.renderView.origin + nAxis[0] + nAxis[1] - nAxis[2];
		corners[3] = rg.renderView.origin + nAxis[0] - nAxis[1] - nAxis[2];
		corners[4] = rg.renderView.origin + fAxis[0] + fAxis[1] + fAxis[2];
		corners[5] = rg.renderView.origin + fAxis[0] - fAxis[1] + fAxis[2];
		corners[6] = rg.renderView.origin + fAxis[0] + fAxis[1] - fAxis[2];
		corners[7] = rg.renderView.origin + fAxis[0] - fAxis[1] - fAxis[2];

		// Compute the split center
		center.Clear();

		for (j = 0; j < 8; j++)
			center += corners[j];

		center /= 8.0f;

		// Compute the split radius
		radius = 0.0f;

		for (j = 0; j < 8; j++){
			distance = center.DistanceSqr(corners[j]);

			if (distance > radius)
				radius = distance;
		}

		radius = glqMath::SqrtFast(radius) + 8.0f;

		// Compute the split bounds in light space
		xCenter = xVector[0] * center[0] + xVector[1] * center[1] + xVector[2] * center[2] + xVector[3];
		yCenter = yVector[0] * center[0] + yVector[1] * center[1] + yVector[2] * center[2] + yVector[3];

		xMin = xCenter - radius;
		xMax = xCenter + radius;

		yMin = yCenter - radius;
		yMax = yCenter + radius;

		// Set up the split
		dl->numShadowSplits++;

		dl->shadowSplitScales[i][0] = 64.0f / glqMath::Ceil(64.0f / (2.0f / (xMax - xMin)));
		dl->shadowSplitScales[i][1] = 64.0f / glqMath::Ceil(64.0f / (2.0f / (yMax - yMin)));

		dl->shadowSplitBiases[i][0] = glqMath::Ceil(((xMax + xMin) / (xMax - xMin)) * xScale) / xScale;
		dl->shadowSplitBiases[i][1] = glqMath::Ceil(((yMax + yMin) / (yMax - yMin)) * yScale) / yScale;
	}
}


// ============================================================================


/*
 ==================
 R_AddDrawLight
 ==================
*/
static void R_AddDrawLight (light_t *light, material_t *material, bool viewInLight){

	drawLight_t	*dl;
	float		*registers;
	int			index;

	if (material->lightType == LT_GENERIC || material->lightType == LT_AMBIENT)
		index = 0;
	else if (material->lightType == LT_BLEND)
		index = 1;
	else {
		if (viewInLight)
			index = 3;
		else
			index = 2;
	}

	// Add a new draw light
	if (rg.numDrawLights[index] == rg.maxDrawLights[index]){
		Com_DPrintf(S_COLOR_YELLOW "R_AddDrawLight: overflow\n");
		return;
	}

	dl = (drawLight_t *)R_FrameAlloc(sizeof(drawLight_t));

	// Fill it in
	dl->light = light;
	dl->material = material;

	// Set up the scissor
	R_SetupScissor(dl);

	if (!dl->scissor.Size())
		return;

	// Set up the shadow LOD
	R_SetupShadowLOD(dl);

	// Set up the shadow cube bits if needed
	R_SetupCubeBits(dl);

	// Set up the shadow splits if needed
	R_SetupShadowSplits(dl);

	// Evaluate material registers
	dl->registers = registers = (float *)R_FrameAlloc(material->numRegisters * sizeof(float));

	R_EvaluateRegisters(material, rg.viewParms.floatTime, light->l.materialParms, light->l.soundEmitterHandle, registers);

	// Determine fog plane visibility
	if (light->data.fogPlane.PointOnSide(rg.renderView.origin) != PLANESIDE_BACK)
		dl->fogPlaneVisible = false;
	else {
		dl->fogPlaneVisible = true;

		// If the vis bounds don't intersect it, the fog plane is not visible
		if (rg.viewParms.primaryView){
			if (light->data.fogPlane.BoundsOnSide(rg.viewParms.visBounds) != PLANESIDE_CROSS)
				dl->fogPlaneVisible = false;
		}
	}

	// Determine light shafts visibility
	if (r_lightShafts->integerValue && light->l.type != RL_DIRECTIONAL && light->l.volumeIntensity && material->lightType == LT_GENERIC)
		dl->lightShaftsVisible = true;
	else
		dl->lightShaftsVisible = false;

	// Generate light surfaces
	R_GenerateLightSurfaces(dl);

	// Add the draw light to the list
	rg.drawLights[index][rg.numDrawLights[index]++] = dl;

	if (light->data.precached)
		rg.pc.staticLights++;
	else
		rg.pc.dynamicLights++;
}

/*
 ==================
 R_AddLights
 ==================
*/
static void R_AddLights (){

	light_t	*light;
	int		cullBits;
	bool	viewInLight;

	if (r_skipLights->integerValue)
		return;

	// Add all the lights
	for (light = rg.scene->activeLight.next; light != &rg.scene->activeLight; light = light->next){
		// Development tool
		if (r_singleLight->integerValue != -1){
			if (r_singleLight->integerValue != light->index)
				continue;
		}

		// Check for view suppression
		if (!r_skipSuppress->integerValue){
			if (!(light->l.allowInView & rg.viewParms.viewType))
				continue;
		}

		// Check the detail level
		if (light->l.detailLevel > r_lightDetailLevel->integerValue)
			continue;

		// Set up the light data
		R_SetupLightData(rg.scene, &light->l, &light->data, rg.viewParms.primaryView);

		// Cull
		if (!r_skipLightCulling->integerValue){
			cullBits = R_CullLightBounds(&light->data, rg.viewParms.planeBits);

			if (cullBits == CULL_OUT)
				continue;

			if (cullBits != CULL_IN){
				if (R_CullLightVolume(&light->data, cullBits) == CULL_OUT)
					continue;
			}
		}

		// Determine if the view is inside the light volume
		viewInLight = R_ViewInLightVolume(&light->data);

		// Mark as visible for this view
		light->viewCount = rg.viewCount;

		// Add the draw light
		R_AddDrawLight(light, light->data.material, viewInLight);
	}
}


// ============================================================================


/*
 ==================
 R_AllocDrawLights
 ==================
*/
void R_AllocDrawLights (){

	rg.numDrawLights[0] = rg.firstDrawLight[0] = 0;
	rg.numDrawLights[1] = rg.firstDrawLight[1] = 0;
	rg.numDrawLights[2] = rg.firstDrawLight[2] = 0;
	rg.numDrawLights[3] = rg.firstDrawLight[3] = 0;

	rg.maxDrawLights[0] = MAX_RENDER_LIGHTS;
	rg.maxDrawLights[1] = MAX_RENDER_LIGHTS >> 2;
	rg.maxDrawLights[2] = MAX_RENDER_LIGHTS >> 4;
	rg.maxDrawLights[3] = MAX_RENDER_LIGHTS >> 4;

	rg.drawLights[0] = (drawLight_t **)R_FrameAlloc(rg.maxDrawLights[0] * sizeof(drawLight_t *));
	rg.drawLights[1] = (drawLight_t **)R_FrameAlloc(rg.maxDrawLights[1] * sizeof(drawLight_t *));
	rg.drawLights[2] = (drawLight_t **)R_FrameAlloc(rg.maxDrawLights[2] * sizeof(drawLight_t *));
	rg.drawLights[3] = (drawLight_t **)R_FrameAlloc(rg.maxDrawLights[3] * sizeof(drawLight_t *));
}

/*
 ==================
 R_GenerateDrawLights
 ==================
*/
void R_GenerateDrawLights (){

	// Add the draw lights
	R_AddLights();

	// Set up the draw surfaces
	rg.viewParms.numDrawLights[0] = rg.numDrawLights[0] - rg.firstDrawLight[0];
	rg.viewParms.numDrawLights[1] = rg.numDrawLights[1] - rg.firstDrawLight[1];
	rg.viewParms.numDrawLights[2] = rg.numDrawLights[2] - rg.firstDrawLight[2];
	rg.viewParms.numDrawLights[3] = rg.numDrawLights[3] - rg.firstDrawLight[3];

	rg.viewParms.drawLights[0] = rg.drawLights[0] + rg.firstDrawLight[0];
	rg.viewParms.drawLights[1] = rg.drawLights[1] + rg.firstDrawLight[1];
	rg.viewParms.drawLights[2] = rg.drawLights[2] + rg.firstDrawLight[2];
	rg.viewParms.drawLights[3] = rg.drawLights[3] + rg.firstDrawLight[3];

	rg.pc.lights += rg.viewParms.numDrawLights[0] + rg.viewParms.numDrawLights[1] + rg.viewParms.numDrawLights[2] + rg.viewParms.numDrawLights[3];

	// The next view rendered in this frame will tack on after this one
	rg.firstDrawLight[0] = rg.numDrawLights[0];
	rg.firstDrawLight[1] = rg.numDrawLights[1];
	rg.firstDrawLight[2] = rg.numDrawLights[2];
	rg.firstDrawLight[3] = rg.numDrawLights[3];
}